/*************************************************************************
	> File Name: 001.List_to_BinaryTree.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 三  9/ 8 17:57:03 2021
 ************************************************************************/

// 广义表转二叉树

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 【要求】将广义表还原构建为一棵二叉树。
 * 【思路】
 * 广义表是用括号嵌套来表示的，而对于括号这样的问题，可以使用栈来解决。根据左括号入栈、右括号出栈。
 * 从左到右遍历字符串，遇到非括号字符封装成一个二叉树结点信息，记录该结点的地址，遇到左括号，将当前结点入栈；下一个非括号字符也封装成一个二叉树结点，其父节点就是栈顶元素。
 * 需要判断它是左孩子还是右孩子，可以根据逗号。如果没遇到逗号，就是左孩子，取出栈顶元素，将栈顶元素的左孩子的指向该结点；遇到右括号，出栈。
 */

typedef struct Node { //二叉树结点
    char data;
    struct Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root; //根结点
    int n; //当前节点个数
} Tree;

typedef struct Stack {
    Node **data; //开辟一片连续的存储空间，每个位置都是存储的Node *这样的地址
    int top; //栈顶
    int capacity; //容量
} Stack;

/*
 * 树结点的创建
 */
Node *createNewNode(char val) { 
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->lchild = NULL;
    p->rchild = NULL;
    return p;
}

/*
 * 树的初始化
 */
Tree *initTree() {
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    tree->root = NULL;
    tree->n = 0;
    return tree;
}

/*
 * 栈的初始化
 */
Stack *initStack(int n) {
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->data = (Node **)malloc(sizeof(Node *) * n);
    s->top = -1;
    s->capacity = n;
    return s;
}

/*
 * 获取栈顶元素
 */
Node *top(Stack *s) {
    return s->data[s->top];
}


/*
 * 判断栈是否为空
 */
int isEmpty(Stack *s) {
    return s->top == -1;
}

/*
 * 入栈
 */
int push(Stack *s, Node *val) {
    if (s == NULL) return -1;
    if (s->top == s->capacity - 1) return -1;
    s->data[++(s->top)] = val;
    return 0;
}


/*
 * 出栈
 */
int pop(Stack *s) {
    if (s == NULL) return -1;
    if (isEmpty(s)) return -1;
    s->top--;
    return 0;
}

/*
 * 栈的销毁
 */
void destroyStack(Stack *s) {
    if (s == NULL) return ;
    free(s->data);
    free(s);
    return ;
}

/*
 * 二叉树结点的销毁
 */
void destroyNode(Node *node) {
    if (node == NULL) return ;
    destroyNode(node->lchild);
    destroyNode(node->rchild);
    free(node);
    return ;
 }

/*
 * 二叉树的销毁
 */
void destroyTree(Tree *tree) {
    if (tree == NULL) return ;
    destroyNode(tree->root);
    free(tree);
    return ;
}

/*
 * 广义表转二叉树
 */
 Node *buildNode(const char *str, int *node_cnt) {
    Stack *s = initStack(strlen(str));
    Node *temp = NULL;
    Node *p = NULL; //p记录根结点，即栈中最后弹出的元素
    int flag = 0;
    while (str[0]) {
        switch (str[0]) {
            case '(':
                push(s, temp);
                flag = 0;
                break;
            case ')':
                p = top(s);
                pop(s);
                break;
            case ',':
                flag = 1;
                break;
            case ' ': 
                break;
            default:
                temp = createNewNode(str[0]);
                if (!isEmpty(s) && flag == 0) {
                    top(s)->lchild = temp;
                } else if (!isEmpty(s) && flag == 1) {
                    top(s)->rchild = temp;
                }
                ++(*node_cnt);
                break;
        }
        ++str;
    }
    if (p == NULL) p = temp; //只有一个结点时因为没有括号，就没有了入栈操作，故单独判断这种情况 
    destroyStack(s);
    return p;
}

/*
 * 先序遍历
 */
void pre_order_node(Node *node) {
    if (node == NULL) return ;
    printf("%c ", node->data);
    pre_order_node(node->lchild);
    pre_order_node(node->rchild);
    return ;
}

/*
 * 先序遍历：传入根结点
 */
void pre_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("pre_order: ");
    pre_order_node(tree->root);
    printf("\n");
    return ;
}


/*
 * 中序遍历
 */
void in_order_node(Node *node) {
    if (node == NULL) return ;
    in_order_node(node->lchild);
    printf("%c ", node->data);
    in_order_node(node->rchild);
    return ;
}


void in_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("in_order: ");
    in_order_node(tree->root);
    printf("\n");
}

/*
 * 后序遍历
 */
void post_order_node(Node *node) {
    if (node == NULL) return ;
    post_order_node(node->lchild);
    post_order_node(node->rchild);
    printf("%c ", node->data);
    return ;
}

void post_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("post_order: ");
    post_order_node(tree->root);
    printf("\n");
    return ;
}


int main() {
    char str[1000] = {0};
    int node_cnt = 0;
    scanf("%[^\n]s", str);
    Tree *tree = initTree(); //二叉树初始化
    tree->root = buildNode(str, &node_cnt); //广义表转二叉树结点
    tree->n = node_cnt;
    pre_order(tree);
    in_order(tree);
    post_order(tree);
    destroyTree(tree);
    return 0;
}
